package com.lfg.leetcode.leetcode0;

/**
 * 给定一个字符串 s，找到 s 中最长的回文子串
 */
public class No5LongestPalindrome {

    public static void main(String[] args) {
        System.out.println(getLongestPalindrome2("cc"));
//        System.out.println(getLongestPalindrome2("babad"));
    }


    private static String getLongestPalindrome2(String s) {
        int start = 0;
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        int max = 1;
        for (int l = 2; l <= s.length(); l++) {
            for (int i = 0; i < s.length(); i++) {
                int e = l + i - 1;
                if (e >= s.length()) {
                    break;
                }
                if (s.charAt(i) != s.charAt(e)) {
                    dp[i][e] = false;
                } else {
                    if (e - i > 2) {
                        dp[i][e] = dp[i + 1][e - 1];
                    } else {
                        dp[i][e] = true;
                    }
                    if (dp[i][e]) {
                        if (l > max) {
                            max = l;
                            start = i;
                        }
                    }
                }
            }
        }
        return s.substring(start, start + max);
    }
}
